package DP1;

/**
 * 剑指 Offer 63. 股票的最大利润
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，
 * 最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
 */
public class Main6 {
    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};

        System.out.println(maxProfit(prices));
    }

    public static int maxProfit(int[] prices) {
        int res = 0;
        int min = Integer.MAX_VALUE;  // 起始成本
        for (int i = 0; i < prices.length ; i++) {
            min = Math.min(min,prices[i]);
            res = Math.max(res,prices[i]-min);
        }
        return res;
    }


//    public static int maxProfit1(int[] prices){
//        if(prices==null||prices.length<1) return 0;
//
//        int n = prices.length;
//        int[] dp = new int[n];
//        int min = Integer.MAX_VALUE;
//        for (int i = 1; i < n ; i++) {
//            min = Math.min(min,prices[i]);
//            dp[i] = Math.max(dp[i-1],prices[i]-min);
//        }
//
//        int max = Integer.MIN_VALUE;
//        for (int e : dp){
//            max= Math.max(max,e);
//        }
//        return max;
//    }



}
